package com.example.daiyinuo.leetcode;

/**
 * 115题，给定字符串中包含多少子串
 * 字符串的一个子序列是指，通过删除一些（也可以不删除）
 * 字符且不干扰剩余字符相对位置 所组成的新字符串。
 * （例如，"ACE"是"ABCDE"的一个子序列，而"AEC"不是）
 */
public class day1 {
    /**
     * 我们定义dp[i][j]表示t的前i个字符可以由s的前j个字符组成的个数
     * （也可以说是字符串s的前j个字符组成的子序列中，和字符串t的前i个字符组成的字符串一样的有多少 个）
     * 动态规划的三个步骤就是
     * 定义状态 列出递推公式，找出边界条件。
     * 前面两步我们都完 成了，我们来看最后一个。因为空字符串" "是所有字符串的子集，所以当字符串t为空 的时候，dp[0][j]=1;
     */
    public static int numDistinct (String s, String t){
        int sLength = s.length();
        int tLength = t.length();
        int dp[][] = new int[tLength+1][sLength+1];
        for(int j=0;j<=sLength;j++){
            dp[0][j] = 1;
        }
        for (int i=1;i<=tLength;i++){
            for (int j = 1; j <=sLength; j++) {
                //如果字符串t的第i个字符和s的第j个字符一样，
                //那么有两种选择
                if(s.charAt(j-1) == t.charAt(i-1)){
                    dp[i][j] = dp[i-1][j-1]+dp[i][j-1];
                }else{
                    //如果字符串t的第i个字符和s的第j个字符不一样，
                    //我们只能用字符串s的前j-1个字符来计算他包含的数量
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[tLength][sLength];
    }

    public static void main(String[] args) {
        String s = "babgbag", t = "bag";
        System.out.println(numDistinct(s,t));
    }
}
